/**
 * 404. 左叶子之和
 * https://leetcode-cn.com/problems/sum-of-left-leaves/
 */
public class Solutions_404 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);  // output: 24

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(3);
//        root.left.left = new TreeNode(4);
//        root.left.right = new TreeNode(5);  // output: 4

        int result = sumOfLeftLeaves(root);
        System.out.println(result);
    }

    /**
     * 注意审题：要计算是 root 树中所以左叶子节点值的和，而不是所有左子节点的和
     * 叶子节点：没有左右子节点的节点
     */
    public static int sumOfLeftLeaves(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            // 节点对象为空，或者节点是叶子节点时，下面一定没有左叶子节点了
            return 0;
        }
        int res = 0;
        TreeNode leftNode = root.left;
        // 判断左子节点，是否是叶子节点
        if (leftNode != null && leftNode.left == null && leftNode.right == null) {
            res += root.left.val;
        }
        // 遍历左右子树，接收返回的子树下左子节点值的和
        int leftRes = sumOfLeftLeaves(root.left);
        int rightRes = sumOfLeftLeaves(root.right);
        // 左子树中可能有左子节点，右子树中也可能有左子节点
        return leftRes + rightRes + res;
    }
}
